package algorithm.sort;

import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2021/1/30 20:09
 * @Version 1.0
 */
public class HeapSort2 {
    public static void main(String[] args) {
        int[] arr = {8, 3, 2, 14, 5, 6, 3, 2, 7, 1};
        headSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void headSort(int[] arr) {
        //构建大顶堆、一定要从最后一个非叶子节点开始构建
        //从右到左、从下到上
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //构建完大顶堆后 就开始每次将堆顶元素与堆尾元素交换，并舍掉这个最大的堆尾元素。从而大顶堆 实现升序。
        for (int last = arr.length - 1; last > 0; last--) {
            swap(arr, 0, last);
            adjustHeap(arr, 0, last);
        }
    }

    /** 构建大顶堆
     * @param arr
     * @param i      调整大顶堆的开始节点的位置
     * @param length 当前大顶堆的节点个数 也即当前数组的长度
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        //先将当前开始节点的值保存起来
        int temp = arr[i];
        //k初始化为当前开始节点的左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //如果右子节点比左子节点还大，那么就拿右子节点去比较
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            //如果当前节点的左子节点或右子节点比当前节点值大，那么就把左子节点或右子节点的值赋给当前节点
            //并且把对应的下标也赋给当前i ,使得在下一轮比较的过程中 i下标变成了这个左子节点或右子节点。再来比较左子节点或右子节点的子节点和其本身的大小
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                //直接break，说明当前子树当前节点已经满足大顶堆了
                break;
            }
        }
        //这里要记得把开始节点i的值经过调整后放到堆的末尾
        arr[i] = temp;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
